#include <bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f,maxn=1e6+10;
int sum[maxn];
int main()
{
	string s="0";
	while(s.length()<maxn){
		string b=s;
		for(char& c:b) c=c=='0'?'1':'0';
		s+=b;
	}
	for(int i=1;i<maxn;i++) sum[i]=sum[i-1]+(s[i-1]=='1');
	int T,n;
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		printf("%d\n",sum[n]);
	}
	return 0;
}